package com.hardydou.algorithm;


import java.util.Arrays;

/**
 * 排序算法 工具集
 */
public class SortKit {


    /**
     * 冒泡排序
     * 时间复杂度：O(N^2)
     * 空间复杂度：O(1)
     * 原地排序：是
     *
     * @param arrs
     */
    public static void bubble(int[] arrs) {
        for (int i = 0; i < arrs.length - 1; i++) {
            for (int j = 0; j < arrs.length - i - 1; j++) {
                if (arrs[j] > arrs[j + 1]) {
                    int temp = arrs[j];
                    arrs[j] = arrs[j + 1];
                    arrs[j + 1] = temp;
                }
            }
        }
    }

    /**
     * 插入排序(直接)
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     * 原地排序：是
     *
     * @param arrs
     */
    public static void insertSort(int[] arrs) {
        for (int i = 1; i < arrs.length; i++) {
            int tmp = arrs[i];
            for (int j = i - 1; j >= 0; j--) {
                if (tmp < arrs[j]) {
                    arrs[j + 1] = arrs[j];
                    arrs[j] = tmp;
                }
            }
        }
    }

    /**
     * 二分插入排序
     *
     * @param arrs
     */
    public static void insertSortBin(int[] arrs) {

        for (int i = 1; i < arrs.length; i++) {
            int tmp = arrs[i];
            int low = 0, high = i - 1, mid;
            while (low <= high) {
                mid = (low + high) / 2;
                if (arrs[mid] > tmp) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            for (int j = i; j > low; j--) {
                arrs[j] = arrs[j - 1];
            }
            arrs[low] = tmp;


        }

    }

    /**
     * 选择排序
     * 1、遍历i-len 数组，找出最小值游标。
     * 2、将最小值与i交换。
     *
     * @param arrs
     */
    public static void selectionSort(int[] arrs) {
        for (int i = 0; i < arrs.length - 1; i++) {
            int tmpIdx = i;
            for (int j = i + 1; j < arrs.length; j++) {
                if (arrs[tmpIdx] > arrs[j]) {
                    tmpIdx = j;
                }
            }
            int tmp = arrs[i];
            arrs[i] = arrs[tmpIdx];
            arrs[tmpIdx] = tmp;
        }
    }

    /**
     * 希尔排序
     *
     * @param arrs
     */
    public static void shellSort(int[] arrs) {
        int len = arrs.length;
        int step = len;
        while ((step = step / 2) > 0) {
            for (int i = step; i < len; i += step) {
                int tmp = arrs[i];
                for (int j = i - step; j >= 0; j -= step) {
                    if (tmp < arrs[j]) {
                        arrs[j + step] = arrs[j];
                        arrs[j] = tmp;
                    }
                }
            }
        }
    }

    /***
     * 归并排序
     *
     * @param arrs
     */
    public static void merge_sort(int[] arrs) {
        merge_c(arrs, 0, arrs.length - 1);
    }

    private static void merge_c(int[] arrs, int l, int r) {
        //中断条件
        if (l >= r) {
            return;
        }
        //中间值
        int m = (l + r) / 2;
        //递归
        merge_c(arrs, l, m);
        merge_c(arrs, m + 1, r);
        //合并
        merge(arrs, l, r, m);
    }

    private static void merge(int[] arrs, int l, int r, int m) {
        int i = l, j = m + 1, q = 0;
        int[] tmp = new int[r - l + 1];
        while (i <= m && j <= r) {
            if (arrs[i] > arrs[j]) {
                tmp[q++] = arrs[j++];
            } else {
                tmp[q++] = arrs[i++];
            }
        }
        int s = i, e = m;
        if (r >= j) {
            s = j;
            e = r;
        }
        for (; s <= e; s++) {
            tmp[q++] = arrs[s];
        }
        for (int n = 0; n < tmp.length; n++) {
            arrs[l + n] = tmp[n];
        }
    }


    /***
     * 快速排序
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(1)
     * 是原地排序
     * @param arrs
     */
    public static void quickSort(int[] arrs) {
        quickSortC(arrs, 0, arrs.length - 1);
    }

    /***
     * 快速排序递归函数
     * @param arrs
     * @param p
     * @param r
     */
    private static void quickSortC(int[] arrs, int p, int r) {
        if (p >= r) {
            return;
        }
        int q = partition(arrs, p, r);
        quickSortC(arrs, p, q - 1);
        quickSortC(arrs, q + 1, r);
    }

    /***
     * 快排分区函数
     * @param arr
     * @param p
     * @param r
     * @return
     */
    private static int partition(int[] arr, int p, int r) {
        int pivot = arr[r];
        int i = p;
        for (int j = p; j < r; j++) {
            if (arr[j] <= pivot) {
                swap(arr, i, j);
                i++;
            }
        }
        swap(arr, i, r);
        return i;
    }

    /**
     * 交换
     *
     * @param arr
     * @param i
     * @param j
     */
    private static void swap(int[] arr, int i, int j) {
        if (i == j) {
            return;
        }
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    /***
     * 计数排序
     * 时间复杂度：O(n)
     * 适用场景：待排序数据，可以分为k个桶，其中k比较小。
     */
    public static void countSort(int[] arrs) {
        int max = 0;
        for (int i = 0; i < arrs.length; i++) {
            if (arrs[i] > max) {
                max = arrs[i];
            }
        }
        //设置桶的数量
        int[] tmp = new int[max + 1];
        //统计每个数字出现个数
        for (int i = 0; i < arrs.length; i++) {
            tmp[arrs[i]]++;
        }
        //累加
        for (int i = 1; i < tmp.length; i++) {
            tmp[i] += tmp[i - 1];
        }
        //申请新的数组空间
        int[] result = new int[arrs.length];
        //依次将待排序数据放到指定位置
        //必须倒着来
        for (int i = arrs.length-1; i >=0; i--) {
            int pos = tmp[arrs[i]]--;
            result[pos - 1] = arrs[i];
        }
        //拷贝回原数组
        for (int i = 0; i < result.length; i++) {
            arrs[i] = result[i];
        }
    }

    /***
     * 桶排序
     * 时间复杂度：O(n)
     * 适用场景：
     *  a、待排序数列，可以均匀非诚k个桶，
     *  b、适合外部排序，即 内存有限，现将数据分割成有序的文件、然后再讲独立文件在内存进行排序，最后依次合并文件
     * @param arrs
     */
    public static void bucketSort(int[] arrs) {


    }

    /***
     * 基数排序
     * 时间复杂度:O(n)
     * 适用场景：
     *  a、可以按位分割、且位之间递进关系，即 高位大的一定大
     * @param arrs
     */
    public static void radixSort(long[] arrs) {
        long pos = 1;
        for (int i = 0; i < 11; i++) {
            countSort(arrs, pos );
            pos *= 10;
        }
    }

    /**
     * pos=10,100,1000...
     */
    public static void countSort(long[] arrs, long pos) {
        //设置桶的数量
        int[] tmp = new int[10];
        //统计每个数字出现个数
        for (int i = 0; i < arrs.length; i++) {
            int n=(int)(arrs[i]/pos%10);
            tmp[n]++;
        }
        //累加
        for (int i = 1; i < tmp.length; i++) {
            tmp[i] += tmp[i - 1];
        }
        //申请新的数组空间
        long[] result = new long[arrs.length];
        //依次将待排序数据放到指定位置
        //这里必须是 倒着开始
        for (int i = arrs.length-1; i >= 0; i--) {
            int n=(int)(arrs[i] / pos%10);
            int m = tmp[n]--;
            result[m - 1] = arrs[i];
        }
        //拷贝回原数组
        for (int i = 0; i < result.length; i++) {
            arrs[i] = result[i];
        }
    }

}
